package likou;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @description: 贪心算法示例（广播站覆盖问题）
 * @title: GreedyAlgorithm
 * @author: zp
 * @date: 2022/1/28 19:39
 */
public class GreedyAlgorithm {

    public static void main(String[] args) {
        List<String> k1 = Arrays.asList("北京", "上海", "天津");
        List<String> k2 = Arrays.asList("广州", "北京", "深圳");
        List<String> k3 = Arrays.asList("杭州", "上海", "成都");
        List<String> k4 = Arrays.asList("上海", "天津");
        List<String> k5 = Arrays.asList("杭州", "大连");
        List<String> list = new ArrayList<>();
        Map<String,List<String>> map = new HashMap<>();
        list.addAll(k1);
        list.addAll(k2);
        list.addAll(k3);
        list.addAll(k4);
        list.addAll(k5);
        //去重
        list = list.stream().distinct().collect(Collectors.toList());
        map.put("k1",k1);
        map.put("k2",k2);
        map.put("k3",k3);
        map.put("k4",k4);
        map.put("k5",k5);
        List<String> greedyList = greedy(list, map);
        System.out.println(greedyList);
    }
    /**
     * @description: 覆盖方法
     * @author: zp
     * @date: 2022/2/4 19:50
     * @param: list 需要覆盖的集合
     * @param: lists 所有电台和覆盖的地区
     * @return: java.util.List<java.util.List<java.lang.String>> 返回电台覆盖的集合
     */
    public static List<String> greedy(List<String> list, Map<String,List<String>> map) {
        List<String> greedyList = new ArrayList<>();
        List<String> temp;
        List<String> maxList;
        Map<String,Integer> countMap = new HashMap<>();
        int max;
        int count;
        String maxName = null;
        //判断是否所有的地区是否已经覆盖 如果没有继续循环寻找
        while (list.size()!=0){
            countMap.clear();
            //遍历每个集合的 获取权重
            for (Map.Entry<String, List<String>> entry : map.entrySet()) {
                count = 0;
                temp = entry.getValue();
                for (String s : temp) {
                    if (list.contains(s)) {
                        count++;
                    }
                }
                //当集合里面都不存在 就不需要把子集添加到集合当中
                if(count!=0){
                    countMap.put(entry.getKey(),count);
                }
            }

            if(countMap.size()==0){
                break;
            }
            max = 0;
            //遍历权重集合 获取权重最大的那个子集合 获取之后在大集合当中删除这个子集合
            for (Map.Entry<String, Integer> entry : countMap.entrySet()) {
                if (max < entry.getValue()) {
                    max = entry.getValue();
                    maxName = entry.getKey();
                }
            }
            maxList = map.get(maxName);
            greedyList.add(maxName);
            map.remove(maxName);
            //把子集合当中的地区排除 当需要覆盖地区的集合数据为空的时候 说明所有地区已经被覆盖
            //在需要覆盖地区集合当中删除这个已经覆盖的地区
            for (String s : maxList) {
                list.remove(s);
                if (list.size() == 0) {
                    return greedyList;
                }
            }
        }
        return new ArrayList<>();
    }
}
